package com.xieyong.leetcode;

import java.util.*;

public class Leetcode1948 {
    public static void main(String[] args) {
        Leetcode1948 leetcode1948 = new Leetcode1948();
        List<List<String>> paths = new ArrayList<>();
        List<String> path1 = new ArrayList<>();
        path1.add("a");
        List<String> path2 = new ArrayList<>();
        path2.add("b");


        paths.add(path1);
        paths.add(path2);
        List<List<String>> lists = leetcode1948.deleteDuplicateFolder(paths);
        for (List<String> list : lists) {
            for (String s : list) {
                System.out.print(s + "  ");
            }
        }
    }

    class Node {
        public String val;
        public Map<String, Node> children = new HashMap<>();
    }

    public List<List<String>> deleteDuplicateFolder(List<List<String>> paths) {
        Node root = new Node();
        for (List<String> path : paths) {
            Node cur = root;
            for (String s : path) {
                cur.children.putIfAbsent(s, new Node());
                cur = cur.children.get(s);
            }
        }
        Map<String, Integer> map = new HashMap<>();
        dfs(root,map);
        List<List<String>> res = new ArrayList<>();
        List<String> path = new ArrayList<>();
        dfs2(root,map,res,path);
        return res;
    }

    private void dfs2(Node node, Map<String, Integer> map, List<List<String>> res, List<String> path) {
        if (map.getOrDefault(node.val, 0) > 1) return;

        if (!path.isEmpty()) {
            res.add(new ArrayList<>(path));
        }

        for (Map.Entry<String, Node> entry : node.children.entrySet()) {
            path.add(entry.getKey());
            dfs2(entry.getValue(), map, res, path);
            path.remove(path.size() - 1);
        }
    }

    private void dfs(Node node, Map<String, Integer> showTime) {
        if (node.children.isEmpty()) {return;}

        List<String> childrenStr = new ArrayList<>();
        for (Map.Entry<String, Node> stringNodeEntry : node.children.entrySet()) {
            dfs(stringNodeEntry.getValue(), showTime);
            childrenStr.add(stringNodeEntry.getKey() + "(" + stringNodeEntry.getValue().val + ")");
        }

        Collections.sort(childrenStr);
        StringBuffer sb = new StringBuffer();
        for (String s : childrenStr) {
            sb.append(s);
        }
        node.val = sb.toString();
        showTime.put(node.val, showTime.getOrDefault(node.val, 0) + 1);
    }

}
